1. Field of Invention The present invention relates to signal processing generally and more particularly to the writing and reading of streaming data involving very large data sets to and from persistent mass storage.
2. Description of Related Art
As computer-based simulations of dynamic systems such as integrated circuit designs become larger and more complex, the sheer volume of data generated by such simulations is rapidly exhausting the ability of analysis tools to manage and post-process such data. Modern analog/mixed signal simulators produce very large simulation waveform datasets. Recent simulation technologies allow for the creation of datasets with millions of signals, each with millions, or even billions of samples per signal. For example, a large simulation signal may include on the order of 107 or 108 samples/signal. A wide simulation data set may include on the order of 10K or more signals. Specifically, for instance, a PLL circuit design may include on the order of 25 nodes for which a signal is produced during a simulation and in which each signal comprises on the order of 100M samples and are iterated over 1000 different temperature conditions and operating points. Moreover, a CPU circuit design may include on the order of 10M nodes for which a signal is produced during a simulation and in which each signal comprises on the order of 40K samples.
Existing signal database and post-processing technologies have significantly lagged the performance and scalability requirements of these leading edge circuit designs as well as the next generation designs. With the advent of nanometer technology, the analysis of parasitic effects has become more important in verifying design functionality, timing and power. This requires simulation tools not only to handle large memories but also to analyze the effects of hundreds of millions of parasitic elements. As a result, there has been a need for improvements in storage, retrieval, generation, display, and post-analysis of very large simulation waveform data sets.
Thus, a significant challenge in representing very high volume time-series data is organizing and storing the information in a manner that permits high-performance reading, writing, and visualization of such data. While some conventional schemes allow for rapid output and storage of very large data sets, they generally do not facilitate rapid reading of the stored data. Conversely, other existing schemes may allow for rapid retrieval of data, but do not facilitate rapid storage of the data. Still others may provide both rapid reading and writing of data, but do not facilitate post-analysis, manipulation, or visualization of stored data.
There are several different existing approaches to the management of very large and/or wide simulation waveform data sets. For example, one approach referred to as ‘Parameter Storage Format’ (PSF) involves output of simulation data quickly to the storage media with minimal organization, data indexing, and with minimal or no support for downstream post-processing requirements. Another approach involves indexing and organizing data into logical sectors with database tables to speed the search process for location and retrieval of data during post-processing stages. Yet another approach optimizes the storage of data structures to speed up access and retrieval of specific time segments or specific data resolutions. Still another existing approach involves a hierarchical waveform database that involves a combination of the PSF and indexing and organizing approaches.
Unfortunately, there have been shortcomings with each of these prior approaches. For example, a limitation of PSF is slow read performance for post-processing, analysis, and visualization tasks that require the ability to quickly find and retrieve desired data segments on demand. A limitation of the above-mentioned indexing and organizing approach is the inability to retrieve whole or specific data segments at arbitrary resolutions required for fast waveform display rendering or post-analysis. That is, post-processing is performed at the full resolution that the data was stored in, not the desired resolution when being analyzed or displayed. A limitation of a hierarchical waveform database is the large memory overhead required to generate hierarchical tree structures as well as the inability to scale to very large signal sets (e.g. on the order of one million signals or more).
A fundamental challenge to each of these prior approaches has been the need to achieve improved storage and retrieval of very large simulation waveform data sets without significantly degrading the performance of the simulation engine that generates such data sets. More particularly, there has been a need to write to mass memory the data produced by the simulator without slowing the simulator and to do so in a manner that facilitates retrieval and post-processing. In general, fast writes can be achieved through FIFO buffered data with block I/O system calls. Conversely, fast reads can be achieved by organizing and structuring the data to add more retrieval information such index tables or hints. However, memory management involved with structuring the data at write-time to improve read-time and/or post-processing performance can lead to consumption of CPU and memory overhead shared by the simulator, resulting in reduced simulator performance.
Of course, there are numerous existing techniques to organize data storage so as to achieve efficient data retrieval. FIG. 1 is an illustrative drawing representing a typical prior linked list structure used to search for data ordered in a list structure. Each element may correspond to a block of data stored in computer readable memory, for example. A plurality of ordered elements is linked in sequential order in a list in which each given element in the list includes a pointer indicative of a location of a next sequential element in the list. That is, a pointer points to a memory location, or file offset location, of a next sequential element in the list, and in which an element sequentially preceding such given element in the list structure points to a memory location of the given element. Thus, for example the pointer in the element labeled 17 points to the memory location of element labeled 19, and the pointer in element labeled 19 points to the memory location of element labeled 21. Retrieving an element linked in such a list from memory typically involves sequentially traversing the list element-by-element until the sought after element is located. For instance, locating element labeled 21 typically would involve starting at the head of the list labeled “a” and following pointers to elements 3, 6, 7, 9, 12, 17, 19 and 21, respectively. Unfortunately locating an element in a sequential linked list such as that of FIG. 1 is relatively inefficient, O(n), and slow especially for large lists.
The skip list is an example of an improved prior technique to organize data for efficient retrieval. FIG. 2 is an illustrative drawing representing a skip list structure. In simple terms, a skip list is a sorted linked list. However, while the nodes in an ordinary linked list such as that of FIG. 1 have one ‘next’ pointer, the elements of a skip list may have multiple ‘next’ pointers, referred to as forward references. Moreover, the number of forward references for a given element in a linked list may be determined probabilistically. Skip lists allow intermediate elements in a list between a given element and a sought after element to be skipped resulting in expected O(log n) performance, which is a significant improvement over ordinary linked lists. A search through a skip list involves traversing forward pointers that do not overshoot the sought after element. When no more progress can be made at a current level of forward pointers, the search moves down to a next level of pointers.
For example, searching for the element labeled 21 in the skip list of FIG. 2 involves starting at forward skip list tail “Tf” and following its top level pointer (L3), which is indicative of the location, such as actual memory location or file offset location, of the element labeled 6 and then following the next lower level pointer (L2) in element labeled 6, which points forward to the memory location or file offset location of element labeled 25. Element 25 is disposed after the sought after element 21 in the skip list, and the L2 pointer to the location of element labeled 25 overshoots the sought after element 21. Thus, the search moves forward to the next level pointer (L 1) in element 6, which points to the location of element labeled 9. Element 9 is disposed in the list before the sought after element 21. Therefore, the search continues at that same level L1 from element 9. The L1 pointer in element 9 points forward to the element labeled 17. The L1 pointer of element 17 points forward to the location of element 25. Since the L1 pointer from the element labeled 17 overshoots the sought after element labeled 21, the search moves down to the LO pointer of element 17, which points to element labeled 19. The LO pointer of element 19, in turn, points to the sought after element labeled 21. Therefore, the search is complete.
Modified skip lists that use bi-directional pointers and child pointers have been proposed. This proposed approach showed improved search performance in certain cases. However, this can be a disadvantage in computing environments where memory overhead is a critical issue.
Thus, there has been a need for improvement in the processing of very large, very wide data sets that more efficiently achieves an organization of the data in the course of writes to persistent storage that facilitates subsequent efficient retrieval and post-processing of the data. The present invention meets this need.